package likou;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/06/24 09:29
 */
public class _32 {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())()()("));
    }

    public static int longestValidParentheses(String s) {
        int max = 0;
        Deque<String> deque = new LinkedList<>();
        Deque<Integer> list = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (deque.size() == 0 && c == ')') {
                list.offerLast(0);//加墙
                continue;
            }
            if (c == '(') {
                deque.offerLast("(");
                list.offerLast(0);//加墙
                continue;
            }
            if (c == ')') {
                deque.pollLast();
                int now = 0;
                //允许打破一堵墙  list.peek()==0 , p为true表示未打破
                boolean p = true;
                while (list.size() > 0 && (p || list.peekLast() != 0)) {
                    if (list.peekLast() == 0) {
                        p = false;
                    }
                    now += list.pollLast();
                }
                now += 2;
                list.offerLast(now);
                max = Math.max(max, now);
            }
        }
        return max;
    }
}
